#include <stdio.h>
typdef int DataType;
void InsertSortWithGap(DataType* arr, int n, int gap)
{   // 带步长(gap)的插入排序, 用于排序指定 gap 时的小数组
    // 当 gap == 1 时, 取到的就是所有元素
    // 由于添加了 gap, 这里 i 指的不再是有序序列的长度
    int i = gap;
    
    while (i < n)
    {
        DataType temp = arr[i];
        int j = i - gap;
        for (; j >= 0 && arr[j] > temp; j -= gap)
        {
            arr[j + gap] = arr[j];
        }

        arr[j + gap] = temp;
        i++;
    }
}
void ShellSort(DataType* arr, int n)
{   // 这里的 gap 计算使用每次减半的方式, 还有其它更高效的计算方式



    for (int gap = n / 2; gap > 0; gap /= 2)
    {
        InsertSortWithGap(arr, n, gap);
    }
}

